import java.util.Arrays;

public class 找出第K小的数对距离 {
    //https://leetcode.cn/problems/find-k-th-smallest-pair-distance/description/
    public int smallestDistancePair(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        //二分差值
        int l = 0;
        int r = nums[n - 1] - nums[0];
        while(l < r){
            int mid = (l + r) / 2;
            //f函数传mid差值的数量有几个
            if(f(nums,mid) > k){
                r = mid - 1;
            }else{
                l = mid;
            }
        }
        return l;
    }

    private int f(int[] nums, int mid) {
        int left = 0;
        int ret = 0;
        for (int right = 1; right < nums.length; right++) {
            if(nums[right] - nums[left] <= mid){
                ret++;
            }else{
                left++;
            }
        }
        return ret;
    }
}
